package main

import (
	"fmt"
	"strconv"
	"strings"
)

func main_evalRPN() {
	token := []string{"10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"}
	v := evalRPN(token)
	fmt.Println(v)
}

// 150 逆波兰表达式 https://leetcode.cn/problems/evaluate-reverse-polish-notation
func evalRPN(tokens []string) int {
	stack := &stackDto[int]{}
	// 遍历
	for i := range tokens {
		switch tokens[i] {
		case "+":
			v1 := stack.Pop()
			v2 := stack.Pop()
			stack.Push(v1 + v2)
		case "-":
			v1 := stack.Pop()
			v2 := stack.Pop()
			stack.Push(v2 - v1)
		case "*":
			v1 := stack.Pop()
			v2 := stack.Pop()
			stack.Push(v2 * v1)
		case "/":
			v1 := stack.Pop()
			v2 := stack.Pop()
			stack.Push(v2 / v1)
		default:
			v, _ := strconv.Atoi(tokens[i])
			stack.Push(v)
		}
	}
	// 如果遇到数字 入栈
	// 如果遇到符号 弹出两个值 做计算 入栈
	// 最后出栈
	return stack.Pop()
}

// 71 简化路径 https://leetcode.cn/problems/simplify-path/
func simplifyPath(path string) string {
	pathSlice := strings.Split(path, "/")
	pathStack := &stackDto[string]{}
	for _, p := range pathSlice {
		switch p {
		case ".", "": //不需要处理
		case "..": //回退一个目录
			if !pathStack.IsEmpty() {
				pathStack.Pop()
			}
		default:
			pathStack.Push(p)
		}
	}
	if pathStack.IsEmpty() {
		return "/"
	}
	ans := ""
	for _, p := range pathStack.db {
		ans += "/" + p
	}
	return ans
}

// 判断是否合法的括号对
func isValid(s string) bool {
	sByte := []byte(s)
	stack := []byte{}
	for _, b := range sByte {
		if isLeft(b) {
			stack = append(stack, b)
			continue //左括号入栈
		}
		if len(stack) == 0 || !isMatch(stack[len(stack)-1], b) {
			return false
		}

		stack = stack[:len(stack)-1]
	}
	return len(stack) == 0
}

func isLeft(b byte) bool {
	leftMap := map[byte]bool{
		'(': true,
		'{': true,
		'[': true,
	}
	return leftMap[b]
}

func isMatch(left, right byte) bool {
	matchMap := map[byte]byte{
		'(': ')',
		'{': '}',
		'[': ']',
	}
	return matchMap[left] == right
}

type stackDto[T any] struct {
	db []T
}

// Peek 查看栈顶元素
func (d *stackDto[T]) Peek() T {
	var val T
	l := len(d.db)
	if l == 0 {
		return val
	}
	return d.db[l-1]
}

// Pop 弹出栈顶元素
func (d *stackDto[T]) Pop() T {
	var zero T
	l := len(d.db)
	if l == 0 {
		return zero
	}
	v := d.db[l-1]
	d.db = d.db[:l-1]
	return v
}

// IsEmpty 栈是否为空
func (d *stackDto[T]) IsEmpty() bool {
	return 0 == len(d.db)
}

// Push 入栈
func (d *stackDto[T]) Push(val T) {
	d.db = append(d.db, val)
}
